package demo;

import java.util.Arrays;

public class MyMergeSort {
    static int[] res;
    public static void main(String[] args) {
        int[] arr = {1,0,10,16,-1,5,-18};
        res = new int[arr.length];
        mergeSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    private static void mergeSort(int[] arr, int left, int right) {
        //只有1个元素
        if(left >= right) {
            return;
        }
        //拿到中间值
        int mid = left + (right - left) / 2;

        //递归
        mergeSort(arr, left, mid);
        mergeSort(arr, mid+1, right);

        //合并

        int k = 0;
        int i = left , j = mid+1;
        while (i <= mid && j <= right) {
            res[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
        //处理边界情况
        while (i <= mid) {
            res[k++] = arr[i++];
        }
        while (j <= right) {
            res[k++] = arr[j++];
        }
        //填回值
        for(int n = left; n <= right; n++) {
            arr[n] = res[n - left];
        }
    }
}
